The outsourcing of computation has emerged as a common practice for enterprises and individuals, especially in the cloud setting. For example, an owner of a data set, often referred to as the source, wants to answer queries over the data set issued by one or more clients or users and, for reasons of scalability and efficiency, chooses to do so by employing a possibly untrusted server on the cloud.
An immediate by-product of outsourcing of data and computation, however, is the need for verification of the correctness of a computation. Such integrity protection is a core security goal in cloud computing. Ensuring that data contents remain intact in the lifetime of an outsourced data set and that query processing is handled correctly, producing accurate and up-to-date answers, lies at the foundation of secure cloud services.
Authenticated data structures provide cryptographically hardened integrity guarantees in distributed or cloud-based data management settings. They support authenticated queries on a data set that is outsourced to a third party and generally untrusted server, by allowing the server to return—along with the answer to a query—a proof that can validate the correct query execution.
C. Papamanthou et al., “Optimal Verification of Operations on Dynamic Sets,” Proc. CRYPTO 2011, 91-110 (2011) and/or United States Patent Publication No. 2012/0030468, entitled “System and Method for Optimal Verification of Operations on Dynamic Sets,” each incorporated by reference herein, describe tools and techniques for Authenticated Set Operations (ASO) for the case of “flat” set operations (i.e., only one set operation, e.g., intersection, of an arbitrary number of sets).
A need therefore exists for authenticated set operations for the class of queries and computations involving hierarchical set operations, over outsourced data, over which an arbitrary number and type of possibly nested set operations are performed to produce the final result. A further need exists for cryptographic protocols for securely verifying the correctness of the produced results.